package cn.chen.算法.十算法;

import java.util.*;

public class GreedyAlgorithm {

    public static void main(String[] args) {

        LinkedList<String> allAreas = new LinkedList<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大莲");

        Map<String, HashSet<String>> map = new HashMap<>();
        HashSet<String> k1 = new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");

        HashSet<String> k2 = new HashSet<>();
        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");

        HashSet<String> k3 = new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");

        HashSet<String> k4 = new HashSet<>();
        k4.add("上海");
        k4.add("天津");

        HashSet<String> k5 = new HashSet<>();
        k5.add("杭州");
        k5.add("大莲");

        map.put("k1", k1);
        map.put("k2", k2);
        map.put("k3", k3);
        map.put("k4", k4);
        map.put("k5", k5);

        List<String> greedy = greedy(map, allAreas);
        System.out.println(Arrays.toString(greedy.toArray()));
    }

    public static List<String> greedy(Map<String, HashSet<String>> radioStation, LinkedList<String> allAreas) {

        // 创建一个ArrayList存放选择的广播台
        List<String> chooseRadio = new ArrayList<>();

        // 定义一个临时集合，用于存放广播台覆盖地区与allAreas重复的地区
        HashSet<String> tempSet = new HashSet<>();

        // 定义一个maxKey，保存在一次遍历中，广播台与allAreas重复地区数最大的key
        String maxKey = null;
        while (allAreas.size() != 0) {  // allAreas保存的地区越来越少

            // 每执行一次，需要将maxKey清空
            maxKey=null;

            for (String key : radioStation.keySet()) {

                tempSet.clear();    // 清空，以免造成影响
                HashSet<String> keyArea = radioStation.get(key);    // 取出key对应的广播台能覆盖的地区
                tempSet.addAll(keyArea);    // 将能覆盖的地区存放到临时集合中，用于计算重复覆盖的数量
                tempSet.retainAll(allAreas);    // 求出tempSet与allAreas 的交集，并且将交集赋值给tempSet

                // 如果当前集合包含的未覆盖的地区比maxKey指向的集合的地区还多，就需要重置maxKey
                /*
                    tempSet.size() > radioStation.get(maxKey).size() 体现贪心算法的特点，每次选择都是最优的
                    1、tempSet.size()：表示当前广播台与allAreas重复地区的数量。
                    2、radioStation.get(maxKey).size()：
                        2.1、maxKey表示的是当前广播台之前的广播台与allAreas重复数量最大的广播台的key。
                        2.2、最大重复数量广播台的地区数量。
                */
                if (tempSet.size() > 0
                        && (maxKey == null
                                    || (maxKey != null
                                            && tempSet.size() > radioStation.get(maxKey).size()))) {

                    maxKey = key;
                }
            }
            if (maxKey != null) {

                chooseRadio.add(maxKey);
                // 将maxKey指向的地区从allAreas中清除
                allAreas.removeAll(radioStation.get(maxKey));
            }
        }
        return chooseRadio;
    }
}
